Alfonso berkhidmat di Afrika Utara selama 10 tahun. Di sana, beliau peroleh pengalaman dalam bidang perang daripada kempen-kempen menentang pihak Muslim dan Uthmaniyah.[22]

Pada tahun 1471, di bawah perintah Afonso V dari Portugal, beliau hadir dalam penaklukan Tangier dan Arzila di Maghribi,[22] dan berkhidmat sebagai seorang pegawai selama beberapa tahun. Pada tahun 1476 beliau menjadi pengiring Putera John dalam perang menentang Kerajaan Kastil, di Semenanjung Iberia, dan dalam Perang Toro. Alfonso terlibat dalam sebuah kempen di semenanjung Itali pada tahun 1480 untuk menyelamatkan baginda Fernando II dari Aragón daripada serangan Uthmaniyah di Otranto.[13] Apabila Alfonso pulang pada tahun 1481, Putera John ditabalkan sebagai Raja John II manakala Alfonso dikurniakan pangkat Pegawai Kendera (Master of the Horse, 'penjaga kuda') atas segala jasanya, dan ketua pengiring diraja (estribeiro-mor) yang beliau pegang sepanjang pemerintahan baginda John II (1481–95).[22][25] Pada tahun 1489, beliau kembali ke Afrika Utara sebagai panglima pertahanan kota Graciosa, sebuah pulau di sungai Luco berhampiran bandar Al-Araisy, Maghribi. Pada tahun 1490 pula, beliau jadi seorang hulubalang kepada Raja John II, dan kemudian pulang ke Arzila pada tahun 1495, tempat di mana saudaranya Martim mati berperang bersamanya dahulu.

Alfonso mencapai kejayaan dalam banyak kempen perang di Afrika dan Laut Mediterranean, tetapi Asialah tempat yang paling terjejas akibat beliau.[22][25]

Kembara pertama ke India, 1503

Zamorin dari Kalikut

Baginda Manuel I dari Portugal berasa segan terhadap Alfonso semasa pertabalan baginda. Kerana Alfonso kawan kepada mendiang Raja John II tambahan pula Alfonso tujuh belas tahun lagi tua daripada baginda. Pada 6 April 1503, lapan tahun kemudian, Alfonso sertai operasi ke India bersama sepupu beliau Francisco de Albuquerque. Setiap seorang menakhodai tiga buah kapal, bersama Duarte Pacheco Pereira dan Nicolau Coelho. Mereka melancarkan serangan ke atas Zamorin dari Kalikut (Calecute, Kozhikode) dan berjaya meletakkan Raja Negeri Cohin (Cohim, Kochi) di takhta. Sebagai balasan, Raja tersebut membenarkan mereka untuk membina sebuah kota Portugis bernama Immanuel (Kota Kochi) dan mulakan perdagangan dengan Quilon (Coulão, Kollam). Semua ini menjadi permulaan Empayar Portugis timur.[26]

Peta Semenanjung Arab menunjukkan Laut Merah dengan Pulau Soqotra (merah) dan Teluk Parsi (biru) dengan Selat Hormuz (Planisfera Cantino, 1502)

Kembara kedua ke India, 1506

Pada Julai 1504, Alfonso pulang dan disambut oleh baginda Raja Manuel I dengan baik. Baginda meletakkan Alfonso sebagai pemerintah kepada lima buah kapal dalam enam belas armada ke India pada tahun 1506 atas jasa Alfonso dalam perancangan Empayar Portugis di Asia, dan diketuai oleh Tristão da Cunha.[26] Rancangan mereka adalah untuk merampas Pulau Soqotra dan dirikan sebuah kota di sana dan tutup perdangangan di Laut Merah. Alfonso menyamar sebagai "ketua nakhoda Pantai Arab", dan belayar di bawah arahan Tristão da Cunha sehingga sampai ke Mozambique.[27] Beliau bawa sepucuk surat berekat dengan misi rahsia yang diperintahkan oleh Raja: setelah selesai misi pertama, beliau kena gantikan wizurai pertama India, Francisco de Almeida, yang penggalnya akan tamat dua tahun lagi.[28] Sebelum berangkat, beliau mengesahkan anaknya lahir pada tahun 1500, dan menulis wasiatnya.

Penaklukan pertama Soqotra dan Hormuz, 1507

Tanggal 6 April 1506, armada berlayar dari Lisbon ke India. Alfonso terpaksa kemudi kapalnya sendiri selepas mualim kapalnya (jurumudi) hilang semasa mula belayar. Di Selat Mozambique, mereka selamatkan Kapten João da Nova, yang mengalami masalah dalam perjalanan balik dari India; kemudian da Nova dan kapalnya, Flor de la mar, sertai armada da Cunha.[29] Dari Malindi di Kenya, da Cunha kirim utusan ke Habsyah. Antara paderi yang dihantar ialah João Gomes, João Sanches dan Sid Mohammed dari Tunisia; dan dari sana, Alfonso berjaya hantarkan mereka ke Tanjung Guardafui (Filuk).[30] Selepas menyerang bandar-bandar Arab di timur Afrika, mereka menawan Soqotra dan bina sebuah kota di Suq untuk dirikan sebuah pengkalan dan hentikan perdagangan antara Laut Merah dan Lautan Hindi. Tetapi empat tahun kemudian, Soqotra terbiar kerana ia bukanlah sebuah pengkalan yang mempunyai apa-apa manfaat kepada rancangan Portugis.[28]

Kubu Hormuz di Pulau Hormuz, Iran

Di Soqotra, Tristão dan Alfonso berpisah: Tristão da Cunha belayar ke India, di mana beliau hulurkan bantuan kepada pihak Portugis yang dikepung di Kannur, sementara Alfonso bawa tujuh kapal dan 500 anak kapal ke Hormuz di Teluk Parsi, yang merupakan salah sebuah pusat dagangan utama di Asia. Dalam perjalanannya, beliau juga takluk bandar-bandar Kuryat, Muscat pada Julai 1507, dan Khaur Fakan yang menerima bandar Kalhat dan Sohar sebagai hadiah. Alfonso tiba di Hormuz pada 25 September dan kemudian menawan negeri tersebut, yang setuju menjadi sebuah negeri ufti kepada Raja Portugis.

Tugu Alfonso de Albuquerque, digambarkan berdiri di atas pedang-pedang untuk melambangkan jawab balasnya di Hormuz

Hormuz dahulunya sebuah negeri ufti kepada Syah Ismail dari Parsi. Dalam suatu peristiwa, beberapa utusan Parsi datang ke Alfonso selepas beliau menakluk Hormuz, dan mengarahnya untuk bayar ufti kepada mereka. Alfonso arahkan orangnya untuk beri sejumlah peluru meriam, panah dan senjata, sambil menempelak mereka, "inilah wang dari Portugal untuk bayar ufti kepada barangsiapa yang berani mintanya dari tanah kuasaan Baginda Manuel, Raja Portugal, Tuan Hindia dan kerajaan Hormuz."[31]

Menurut Brás de Albuquerque, Syah Ismaillah yang mencipta gelaran "Singa Samudera". Alfonso mula membina Kota Our Lady of Victory (boleh diterjemahkan kepada "Kota Dang Wijaya"), yang kemudiannya dinamakan kepada Kota Our Lady of the Conception ("Kota Dang Bunting).[32]

Namun, beberapa pegawai di bawahnya enggan melakukan kerja berat tersebut dan selepas mendakwa Alfonso mengambil kesempatan daripada tugasan sebenarnya, mereka berangkat ke India. Kini Alfonso kehilangan dua buah kapal, tidak punyai sebarang bekalan, dan tidak dapat meneruskan jawatan beliau lagi. Beliau menjarah penduduk di pesisiran selepas terpaksa meninggalkan Hormuz pada Januari 1508 untuk membekalkan penempatan Soqotra. Alfonso kembali ke Hormuz, dan akhirnya belayar ke India.

Ditangkap di Kannur, 1509

Alfonso tiba ke Kannur di persisiran Malabar pada Disember 1508, dan membuka surat berekat yang diutuskan oleh Raja sebelum wizurai Dom Francisco de Almeida, yang akan jadi gabenor selepas Almeida.[28][33][34] Wizurai itu, dengan bantuan pegawai yang tinggalkan Alfonso di Hormuz, mendapat perintah diraja yang sama tetapi enggan patuh, dan membantah kerana penggal beliau tamat pada bulan Januari dan beliau berhasrat untuk tebus kematian anaknya dengan melawan tentera laut Mamluk Amir Husain Al-Kurdi, lalu menolak tawaran Alfonso untuk bertarung demi jawatan tersebut. Alfonso mengelak pergolakan yang jika berlaku pasti mencetuskan perang, dan berpindah ke Kochi dan menantikan perintah lanjut daripada Raja, sambil mengurus rombongan pengiringnya. Beliau dikatakan oleh Fernão Lopes de Castanheda yang beliau berdepan dengan pembangkang yang memihak kepada Almeida dengan sabar. Oleh kerana beliau semakin keseorangan, beliau menulis sepucuk surat kepada Diogo Lopes de Sequeira, yang berlabuh ke India baru-baru itu, tetapi Sequeira sebaliknya menjadi pengikut Almeida. Pada masa yang sama pula, Alfonso menolak cubaan daripada pihak lawan Almeida untuk merampas sahaja kuasanya.[35]

Pada 3 Februari 1509, Almeida berperang dalam Pertempuran Diu menentang armada Mamluk, Uthmaniyah, Zamorin dari Kalikut, dan Sultan Gujarat, untuk menebus nyawa anaknya yang terkorban. Kemenangannya muktamad: Uthmaniyah dan Mamluk meninggalkan Lautan Hindi, melanjutkan usia pemerintahan Portugis seratus tahun lagi. Pada bulan Ogos, setelah sebuah petisyen yang dikemukakan oleh bekas pegawai Alfonso, dengan bantuan Diogo Lopes de Sequeira, Alfonso diguling daripada jawatannya untuk memerintah dan dihantarkan ke dalam tahanan Kota St. Angelo di Kannur.[36][37]

Pada bulan September 1509, Sequeira gagal untuk berhubung dengan Sultan Melaka dan terpaksa meninggalkan 19 banduan Portugis.